// 一道典型的简单树上递归的题
class Solution {
 public:
  TreeNode* invertTree1(TreeNode* root) {
    if (root == nullptr) return nullptr;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
  }
  TreeNode* invertTree2(TreeNode* root) {
    if (root == nullptr) return nullptr;
    stack<TreeNode*> st;
    st.push(root);
    TreeNode* temp;
    while (!st.empty()) {
      temp = st.top();
      st.pop();
      swap(temp->left, temp->right);
      if (temp->left) st.push(temp->left);
      if (temp->right) st.push(temp->right);
    }
    return root;
  }
};